package SortTable;


//直接插入排序  折半插入排序  **希尔排序
public class InsertSort {

    //Show
    public static void ShowArr(int[] arr){
        int len=arr.length-1;
        for (int i=1;i<=len;i++){
            System.out.print(arr[i]+" ");
        }
    }

    //10.2.1 Straight Insertion Sort
    public static void StraightInsertSort(int[] arr){
        //记得长度减1 因为下标从0开始！！ 否则会发生数组越界
        int len=arr.length-1;
        for (int i=2;i<=len;++i){
            if (arr[i]<arr[i-1]){
                arr[0]=arr[i];
                arr[i]=arr[i-1];
                int j;
                for (j=i-2;arr[0]<arr[j];--j){
                    arr[j+1]=arr[j];
                }
                arr[j+1]=arr[0];
            }
        }
        ShowArr(arr);
    }

    //10.2.2 BinaryInserationSort
    public static void BInsertSort(int[] arr){
        int len=arr.length-1;
        for (int i=2;i<=len;i++){
            arr[0]= arr[i];
            int low=1;
            int high=i-1;
            while (low<=high){
                int m=(low+high)/2;
                if (arr[m]< arr[0]){
                    low=m+1;
                }else {
                    high=m-1;
                }
            }
            for (int j=i-1;j>=high+1;j--){
                arr[j+1]=arr[j];
            }
            arr[high+1]= arr[0];
        }
        ShowArr(arr);
    }

    //10.2.3 ShellSort
    public static void ShellSort(int[] arr,int[] dlta){
        int length = dlta.length-1;
        for (int i=0;i<=length;i++){
            ShellInsert(arr,dlta[i]);
        }
        ShowArr(arr);
    }

    private static void ShellInsert(int[] arr,int dk) {
        //前后记录位置的增量是dk，不是1；
        //arr[0]只是暂存单元，不是哨兵！！ 当j<=0时，插入位置已找到。
        int length = arr.length-1;
        for (int i=1+dk;i<=length;i++){
            if (arr[i]<arr[i-dk]){
                    arr[0]=arr[i];
                    int  j;
                    for (j=i-dk;j>0&&arr[0]<arr[j];j-=dk){
                        arr[j+dk]=arr[j];
                    }
                    arr[j+dk]=arr[0];
            }
        }
    }

    public static void main(String[] args) {
        int[] arr={0,2,8,5,7,6,4,3};
        int[] dlta={3,2,1};
        ShellSort(arr,dlta);
    }
}
